﻿#region Declaration

//------------------------------------------------------------------------------
// Compas Information Techonoly Co., Ltd
// The Initial Developer of the Original Code is CompasSolutions.
// All Rights Reserved.
// 
// Contributor(s): _______. 
//------------------------------------------------------------------------------

#endregion

#region Using Directives

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Web;
using System.ComponentModel;

#endregion

namespace QuickDev.Common.Data.Sort
{
    /// <summary>
    /// Implementation of the merge sort algorithm.
    /// </summary>
    public sealed class MergeSort<T>
    {
        private IComparer<T> _comparer;
        private bool _isAscending;
        private List<T> _list;
        private T[] _buffer;

        /// <summary>
        /// Creates a new MergeSort class.
        /// </summary>
        private MergeSort( List<T> list , IComparer<T> comparer , ListSortDirection direction )
        {
            _list = list;
            _buffer = new T[list.Count];
            _comparer = comparer;
            _isAscending = ( direction == ListSortDirection.Ascending );
        }

        /// <summary>
        /// Sorts an IList using the specified comparer and the sort direction.
        /// </summary>
        public static void Sort( List<T> list , IComparer<T> comparer , ListSortDirection direction )
        {
            MergeSort<T> sort = new MergeSort<T>( list , comparer , direction );
            sort._MergeSort( 0 , list.Count - 1 );
        }

        private int Compare( T x , T y )
        {
            if ( _isAscending )
                return _comparer.Compare( x , y );
            else
                return _comparer.Compare( y , x );
        }

        #region Algorithm Implementation

        private void _MergeSort( int firstIndex , int lastIndex )
        {
            int lastRelativeIndex = lastIndex - firstIndex;

            if ( lastRelativeIndex < 1 )
                return;

            int middle = ( lastRelativeIndex / 2 ) + firstIndex;
            int postMiddle = middle + 1;

            _MergeSort( firstIndex , middle );
            _MergeSort( postMiddle , lastIndex );

            Merge( firstIndex , middle , postMiddle , lastIndex );
        }

        private void Merge( int leftStart , int leftEnd , int rightStart , int rightEnd )
        {
            int bufferIndex = leftStart;
            int leftIndex = leftStart;
            int rightIndex = rightStart;

            // copy to the buffer the sortable items
            while ( leftIndex <= leftEnd && rightIndex <= rightEnd )
            {
                if ( Compare( _list[leftIndex] , _list[rightIndex] ) > 0 )
                    _buffer[bufferIndex++] = _list[rightIndex++];
                else
                    _buffer[bufferIndex++] = _list[leftIndex++];
            }

            // copy the rest of the items to the buffer

            for ( int i = leftIndex ; i <= leftEnd ; i++ )
                _buffer[bufferIndex++] = _list[i];

            for ( int i = rightIndex ; i <= rightEnd ; i++ )
                _buffer[bufferIndex++] = _list[i];

            // copy the buffer back to the list

            for ( int i = leftStart ; i <= rightEnd ; i++ )
                _list[i] = _buffer[i];
        }

        #endregion

    }
}
